This is a simple algorithm to quickly triangulate a convex to slightly concave polygon to allow for rendering with a triangle list. I did some research online to see if anyone had solved this in a simple plug and play way, but every library out there is a lot heavier than I was looking for, and besides, it's a semi simple problem given my lack of constraints.
I knocked this around for a few hours while I worked on terrain rendering for my latest side project - a sort of tower defence game, and thought it was worth a quick post. It's naive, but definitely serviceable.
Given a polygon of exterior points, we can find a central point. Using this centre as a base, we can iterate around the external points, with the centre point as the fulcrum, giving us a triangulated polygon, ready for rendering.
The sketched diagrams below were my way of working this out.
+-----+
---+--
+-----+
1-----2
---0--
+-----+
+-----4
---3--
+-----5
+-----+
---6--
8-----7
11-----+
---9--
10-----+
0
0, 1, 2 => X, 0, 1
1
3, 4, 5 => X, 1, 2
2
6, 7, 8 => X, 2, 3
3
9, 10, 11 => X, 3, 0
Given a set of Points, we find a centre point of the polygon by adding all points together, then dividing by the total count of points.
Create a placeholder set of vertices that are the perimeter vertices, at this point I set these to a colour as it's easy for placeholder/debugging purposes to be able to see at a glance what is external and what isn't.
The required number of vertices will be the count of perimeter points times 3, so create a new vertex array of that size.
Then run through the first set of vertices again, but this time, we're going to take one set of two at a time, creating a triangle between these and the centrepoint we found earlier.
for (int i = 0; i < _vertices.Length; i++)
{
//for each iteration
//start at centre which is iteration by 3
triangulatedVertices[i * 3].Position = new Vector3(centrePoint, 0);
if (isExternal)
{
triangulatedVertices[i * 3].Color = externalFillGradient;
}
else
{
triangulatedVertices[i * 3].Color = internalFillGradient;
}
if (i == _vertices.Length -1)
{
triangulatedVertices[(i * 3) + 1] = _vertices[i];
triangulatedVertices[(i * 3) + 2] = _vertices[0];
}
else
{
triangulatedVertices[(i * 3) + 1] = _vertices[i];
triangulatedVertices[(i * 3) + 2] = _vertices[i+1];
}
}